package LeetCodeQuestionBank;

import java.util.Arrays;
/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 *
 *
 * 示例 1:
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 *
 * 提示：
 *
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */
public class T003 {

    /**
     * 解题思路 滑动窗口 ，维持一个窗口 并记录这个窗口的的最大长度
     */
    public int lengthOfLongestSubstring(String s) {

        if (s.length() <= 1) {
            return s.length();
        }


        //窗口的开始坐标
        int start = 0;

        //窗口的最大宽度
        int maxlength = 0;

        //记录 字符上次出现的位置 ascII 码 0-127
        int[] last = new int[128];

        //全部赋值为-1
        Arrays.fill(last, -1);

        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {

            char aChar = chars[i];

            start = Math.max(start, last[aChar] + 1); //确定开始的位置

            maxlength = Math.max(maxlength, i - start + 1);

            last[aChar] = i;  //更新字符最近出现的坐标

        }

        return maxlength;

    }

}
